package zijie;

/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 *  
 *
 * 示例:
 *
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true
 * 给定 word = "SEE", 返回 true
 * 给定 word = "ABCB", 返回 false
 *
 */
public class WorldExist_79_33 {
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    private int rows;
    private int cols;
    private int len;
    private boolean[][] visited;
    private char[] charArray;
    private char[][] board;
    public boolean exist(char[][] board, String word) {
        rows = board.length;
        if(rows == 0){
            return false;
        }
        cols = board[0].length;
        visited = new boolean[rows][cols];
        len = word.length();
        this.charArray = word.toCharArray();
        this.board = board;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(dfs(i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int begin){
        if(begin == len - 1){
            return board[x][y] == charArray[begin];
        }
        if(board[x][y] == charArray[begin]){
            visited[x][y] = true;
            for (int[] direction : DIRECTIONS) {
                int newX = direction[0] + x;
                int newY = direction[1] + y;
                if(isArea(newX,newY) && !visited[newX][newY] ){
                    if(dfs(newX,newY,begin + 1)) {
                        return true;
                    }
                }
            }
            visited[x][y] = false;
        }
        return false;

    }

    public boolean isArea(int x,int y){
        return x >= 0 && x < rows && y >= 0 && y <cols;
    }


}
